package com.mgq.algorithm;

import java.util.PriorityQueue;

/**
 * @author MaGuangQi
 * @description: 优先队列
 * https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
 * leetcode 703题
 * 设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。
 * <p>
 * 第k大是什么意思?
 * 举例
 * 比如由 2 3 5 第一大元素是5 第二大是3 第三大是2
 *
 * 解题思路: 因为需要第k大元素,所以需要将排好序的k个最大元素保存起来
 * 使用最小堆可以解决,假如k=3,则最小堆(优先级队列)需要保存3个元素,堆顶元素为最小值,
 * 每次增加元素的时候,如果增加的元素比堆顶元素(最小的元素)大,则堆顶元素出队,新元素入队,重新排序
 * 返回第k大元素,也就是返回堆顶元素,(不好理解,因为k恰好是堆的长度,第k大恰好是堆顶最小的元素)
 * @date 2020-06-17 20:58
 **/
public class MyPriorityQueue {
    PriorityQueue<Integer> queue;
    private int k;
    public MyPriorityQueue(int k, int[] nums) {
        //java中优先级队列默认是最小堆,也就是最小的元素在队头.
        queue = new PriorityQueue<>(k);
        this.k = k;
        for (int i = 0; i < nums.length; i++) {
            //调用自己的add方法
            add(nums[i]);
        }
    }

    public int add(int val) {



        //假设k为3时,queue中有2个元素时,添加第3个元素时,if还会进去.因为此时queue.size=2
        if (queue.size() < k) {
            queue.add(val);
            //队列会保证最小的在队首,也就是添加k个以后的元素的时候需要进行比较
            //如果堆顶的元素都小于新加的元素,将新元素加进来,那么堆顶元素出队.
        } else if (queue.peek() < val) {
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }

    public static void main(String[] args) {
        int[] i=new int[]{4, 5};
        MyPriorityQueue myPriorityQueue = new MyPriorityQueue(3, i);
        //myPriorityQueue.queue.forEach(System.out::println);
        System.out.println(myPriorityQueue.add(8));
        System.out.println(myPriorityQueue.add(2));
        System.out.println(myPriorityQueue.add(5));


    }


}
